
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        queue<pair<TreeNode*,unsigned int>>q;
        unsigned int ret = 1;
        q.push(pair<TreeNode*,unsigned int>(root,0));
        int sz = 1;
        while(q.size())
        {
            unsigned int ln = q.front().second,rn = q.front().second;
            for(int i=0;i<sz;i++)
            {
                if(q.front().first->left)
                {
                    q.push(pair<TreeNode*,unsigned int>(q.front().first->left,q.front().second*2));
                }
                if(q.front().first->right)
                {
                    q.push(pair<TreeNode*,unsigned int>(q.front().first->right,q.front().second*2+1));
                }    
                ln = min(q.front().second,ln);
                rn = max(q.front().second,rn);
                q.pop();
            }
            ret = max(ret,rn-ln+1);
            sz = q.size();
        }
        return ret;
    }
};